[Coding011] LeetCode 2

Add Two Numbers

More coding records

Get the knowledge flowing and circulating! :)

目录

题目: 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

xxxxxxxxxx
3
1
Input: l1 = [2,4,3], l2 = [5,6,4]
2
Output: [7,0,8]
3
Explanation: 342 + 465 = 807.

Example 2:

xxxxxxxxxx
2
1
Input: l1 = [0], l2 = [0]
2
Output: [0]

Example 3:

xxxxxxxxxx
2
1
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
2
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• It is guaranteed that the list represents a number that does not have leading zeros.

代码1

xxxxxxxxxx
66
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
13

14
        // dummy是伪结点（经典步骤）
15
        ListNode dummy = new ListNode(0);  // 用于最后返回，dummy.next
16
        ListNode r = dummy;  // r是在过程中操作的；
17

18
        int res = 0;
19
        int carry = 0;
20

21
        while (l1 != null || l2 != null)
22
        {
23

24
            if (l1 != null && l2 != null)  // 都有值
25
            {
26
                res = l1.val + l2.val + carry;  
27
                l1 = l1.next;
28
                l2 = l2.next;
29
            }
30
            else if (l1 != null && l2 == null)  // 一个有值，一个没有
31
            {
32
                res = l1.val + carry;
33
                l1 = l1.next;
34
            }
35
            else if (l2 != null && l1 == null)  // 一个有值，一个没有
36
            {
37
                res = l2.val + carry;
38
                l2 = l2.next;
39
            }
40

41
            if (res >= 10)  // 如果结果大于等于10，那就进位
42
            {
43
                carry = res / 10;
44
                res = res - carry * 10;
45
            }
46
            else  // 否则不进位
47
            {
48
                carry = 0;
49
            }
50

51
            // 新建一个结点，并且连接在dummy为首结点的这条链后面
52
            ListNode temp = new ListNode(res);
53
            r.next = temp;
54
            r = r.next;
55
        }
56

57
        if (carry > 0)  // 1 + 9 = 10（结果可能超过1位，源自进位位）
58
        {
59
            r.next = new ListNode(carry);  // 所以carry要单独再判断一下
60
            r = r.next;
61
        }
62

63
        return dummy.next;
64
        
65
    }
66
}

代码2

xxxxxxxxxx
39
1

2
class Solution {
3
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
4

5
        // dummy是伪结点（经典步骤）
6
        ListNode dummy = new ListNode(0);  // 用于最后返回，dummy.next
7
        ListNode r = dummy;  // r是在过程中操作的；
8

9
        int res = 0;
10
        int carry = 0;
11

12
        while (l1 != null || l2 != null)
13
        {
14
            // 相比代码1，每次都判断l1, l2
15
            int x = (l1 != null) ? l1.val : 0;  // 条件表达式
16
            int y = (l2 != null) ? l2.val : 0;
17

18
            res = x + y + carry;
19

20
            carry = res / 10;
21
            res = res - carry * 10;
22

23
            r.next = new ListNode(res);
24
            r = r.next;
25

26
            // 相比代码1，每次都判断l1, l2
27
            if (l1 != null) l1 = l1.next;
28
            if (l2 != null) l2 = l2.next;
29

30
        }
31

32
        if (carry > 0)
33
        {
34
            r.next = new ListNode(carry);  // 更节省了！
35
        }
36

37
        return dummy.next;
38
    }
39
}

复杂度分析

有两个链表，复杂度应该是：$O(max(n,m))$$O(max(n,m))$

★ 知识点积累 (Java)

1. dummy伪结点的使用，更熟悉了一点；

   • 先新建dummy结点；

   • 然后用一个指针p指向dummy；

   • 然后只操作这个指针p，dummy不动，这样的话，最后只需要返回dummy即可！

2. 两数之和要有进位位，进位位的经典计算方法

   carry = sum / 10;

   sum = sum - carry * 10;

3. 单链表类的使用

   • 新建一个结点：ListNode temp = new ListNode(val);

   • 链接一个结点：p.next = temp;

4. 条件表达式的使用

   xxxxxxxxxx
   12
   1
   if (l1 != null)
   2
   {
   3
       x = l1.val;
   4
   }
   5
   else
   6
   {
   7
       x = 0;
   8
   }
   9
   
   10
   // 等价于
   11
   
   12
   x = (l1 != null) ? l1.val : 0;